This invention relates to digital signatures. More particularly, this invention relates to the use of digital signatures and certificates for digital signatures in a commercial cryptographic system for enforcing security policies and authorization requirements in a manner that reduces risks to the users.
Public-key cryptography is a modern computer security technology that can support the creation of paperless electronic document systems, providing that the user's digital signature on an electronic document, i.e., the user's electronic authentication and verification of the electronic document, can be given sufficient practical and legal meaning. Such paperless electronic document systems, or "document architectures," will encompass not only trading partners operating under standard bilateral contracts but also global multilateral systems in which any entity can, in theory, correspond with any other entity in a legally provable manner, assuming that proper security controls are observed throughout.
These systems will have enormous commercial significance because, in many cases, cost reductions on the order of 10-to-1 can be realized over current paper transaction procedures. This improvement is sufficiently dramatic such that many organizations would, for economic and competitive reasons, be compelled to use them once their practicality had been demonstrated.
No one disputes that paper is a bothersome anachronism in the electronic world or that verifying pen-and-ink signatures is costly and error-prone. At least with paper, however, the signer retains the basic "contextual controls" of document preparation and physical delivery. On a digitally signed electronic document, on the other hand, a signer controls only the encoded signature. All time, place and manner controls are absent, and nothing distinguishes a valid user signature from one fraudulently produced by another user who somehow obtained the first user's smart card and PIN. It would not take too many multi-million or multi-billion dollar losses to erase all the savings produced by this "newfangled" office-automation technology. Therefore, digital signatures will see early use only in consumer "electronic coin purse" applications, where exposure is low, and in wholesale financial transfers, as to which extremely tight security procedures are already the norm. However, these uses will have little general commercial impact.
Thus far, major corporations and banks have declined to invest in these technologies due to lack of well-defined risk models and auditing standards and due to uncertainties regarding legal and liability issues. Serious investments to commercialize digital signatures will occur only after leading national auditing and legal experts have ruled that these systems contain adequate security controls to warrant reliance in mainstream intra- and inter-corporate business transactions, typically in the $10,000 to $10 million range. In order for this goal to be achieved, security controls must be formulated to reduce the risks of participants in digital signature document systems to the absolute lowest level technically achievable.
There are two types of cryptographic systems in which digital signatures have been used: symmetric and asymmetric cryptosystems. FIG. 1 illustrates the use of symmetric and asymmetric algorithms for encryption. In symmetric (conventional) cryptography, as shown in FIG. 1(a), the sender and recipient of a communication share a secret key 11. This key is used by the sender, the originator of a communication, to encrypt the message 12 and by the recipient of the communication to decrypt the message 13. It may also be used by the recipient to authenticate a message by having the sender use the secret key to compute some function such as a Message Authentication Code (MAC) based upon the message; the recipient thus can be assured of the identity of the originator, because only the sender and the recipient know the secret key used to compute the MAC. DES is an example of a symmetric cryptosystem.
In asymmetric (public key) cryptography, shown in FIG. 1(b), different keys are used to encrypt and decrypt a message. Each user is associated with a pair of keys. One key 15 (the public key) is publicly known and is used to encrypt messages 17 destined for that user, and the other key 16 (the private key) is known only to that user and is used to decrypt incoming messages 18. Since the public key need not be kept secret, it is no longer necessary to secretly convey a shared encryption key between communicating parties prior to exchanging confidential traffic or authenticating messages. RSA is the most well-known asymmetric algorithm.
A digital signature, however, is a block of data appended to a message data unit, and allows the recipient to prove the origin of the message data unit and to protect it against forgery. Some asymmetric algorithms (e.g., RSA) can also provide authentication and non-repudiation through use of digital signatures. In order to sign data, the sender encrypts the data under his own private key. In order to validate the data, the recipient decrypts it with the sender's public key. If the message is successfully decrypted using the sender's public key, the message must originally have been encrypted by the sender, because the sender is the only entity that knows the corresponding private key. Using this method of signing documents, the encrypted message is bound to the signature, because the recipient cannot verify the message without decrypting the signature data block. The signature-encrypted message can then be encrypted to the recipient using the recipient's public key, as usual.
Digital signatures may also be formed using asymmetric encryption algorithms as described below and as illustrated in FIG. 2. To sign a message, the message 20 is first digested (hashed) into a single block 22 using a one-way hash function 21. A one-way hash function has the property that, given the digest, it is computationally infeasible to construct any message that hashes to that value or to find two messages that hash to the same digest. The digest 22 is then encrypted with the user's private key 23, and the result 24 is appended to the encrypted or unencrypted message as its signature 25. The recipient uses the sender's public key 26 to decrypt the signature 25 into the hash digest 22. The recipient also digests (hashes) the message 20, which has been received either unencrypted or encrypted and then decrypted by the recipient, into a block 27 using the same one-way hash function 21 used by the sender. The recipient then verifies 28 the sender's signature by checking that the decrypted hash digest 22 is the same as the hashed message digest 27.
Separating the signature from the message in this way, i.e., not requiring the sender and recipient to encrypt and decrypt the entire message in order to verify the signature, greatly reduces the amount of data to be encrypted. This is important because public key algorithms are generally substantially slower than conventional algorithms, and processing the entire message in order to verify a signature would require a significant amount of time. The signature process also introduces redundancy into the message, which, because the message must hash to the specified digest, allows the recipient to detect unauthorized changes to the message.
A digital signature provides the security services of (a) integrity, because any modification of the data being signed will result in a different digest and thus a different signature; (b) origin authentication, because only the holder of the private key corresponding to the public key used for validation of the signature could have signed the message; and (c) non-repudiation, as irrevocable proof to a third party that only the signer, and not the recipient or its employees, could have created the signature. A symmetric secret key authenticator, e.g. the X9.9 FLAC, does not provide these services, since either of the two parties can create the authenticator using their shared key.
Several of the mechanisms discussed herein assume the ability to attach multiple signatures or cosignatures to a document. RSA Data Security, Inc., "PKCS #7: Cryptographic Message Syntax," 1993, which is hereby incorporated by reference, defines a useful format for this purpose. Each signature structure on a document will contain an indication of the certificate needed to validate the signature along with a bit string containing the actual signature. Additionally, other information relevant to the particular signer may be included in an individual signature computation. This per-signer information may be included in the signature computation as "signature attributes."
In order for one user to identify another user for transmission of a message in a way that ensures the second user's possession of a private key, the first user must be able to obtain the other user's public key from a trusted source. A framework for the use of public key certificates was defined in CCITT, "X.509: The Directory: Authentication Framework," April, 1993 ("X.509"), which is hereby incorporated by reference. These basic public key certificates bind a user's name to a public key and are signed by a trusted issuer called a Certification Authority (CA). Besides containing the user's name and public key, the certificate also contains the issuing CA's name, a serial number and a validity period.
Although X.509 does not impose any particular structure on the CAs, many implementations find it reasonable to impose a hierarchical structure in which each CA (in general) certifies only entities that are subordinate to it. Hence, we can construct a hierarchy of Cas, as shown in FIG. 3, in which the higher level CAs 31 (perhaps banks) sign the certificates 34 of the CAs 32 beneath them (e.g., companies), and the lowest level of CAs 32 sign user 33 certificates 35. At the top of this hierarchy (not shown) are a relatively few other root CAs, perhaps one per country, that may "cross-certify" each other's public keys (root keys).
Various security architectures define mechanisms to construct a certification path through the hierarchy to obtain a given user's certificate and all CA certificates necessary to validate it. These architectures share the common characteristic that a user need trust only one other public key in order to obtain and validate any other certificate. The trusted key may be that of the top-level CA (in a centralized trust model) or of the local CA that issued the user's certificate (in a decentralized model).
Certificates also contain an expiration date. If it is necessary to cancel a certificate prior to its expiration date, such as if the name association becomes invalid or the corresponding private key is lost or compromised, the certificate may be added to the CA's certificate revocation list (CRL) or "hot list." This list is signed by the CA and widely distributed, possibly as part of the CA's directory entry. The certificate remains on the CRL until the certificate's expiration date.
Often certain information concerning an entity or CA needs to be made available in a trusted manner. In a secure X.500 Directory, this information would be retrieved via standard Directory operations and the result would be signed by the Directory. In the absence of such a secure X.500 implementation, this information is placed in an attribute certificate, which is signed by a CA in the same manner as the public key certificate. Attribute certificates would be created on presentation of the proper credentials by the user. For example, the user would present his public key certificate and prove he possesses the corresponding private key, as one form of identification. Attribute certificates are linked to the user's basic public key certificate by referencing the basic certificate's serial number and are revoked by an identical parallel CRL mechanism. Attribute certificates are discussed further in ANSI X9F1, "X9.30 Part 3: Certificate Management for DSA," June, 1994, and U.S. Pat. Nos. 4,868,877, 5,005,200 and 5,214,702, which are all hereby incorporated by reference.
An attribute certificate is a structure separate from a public key certificate because proper separation of duties may often require that the CA that issues the attribute certificate be different than the CA that issues the public key certificate. A central CA might rarely of itself possess the required security or authority to "sign for" all of a user's authorizations. Having separate CAs generate various types of attribute certificates distributes risks more appropriately. In addition, the defined attributes may not be required for all domains, networks or applications. The need for these attributes and for additional domain-specific attributes is determined by each domain.
The user's basic public key certificate remains X.509 compatible, allowing its use with other applications and allowing use of commercial products for certificate generation.
It is desirable to be able to construct a trusted organization that utilizes digital signature and certificate mechanisms to enforce a security policy defined by rules within this organizational structure.
It is also desirable to use digital signature and certificate mechanisms to encode industry-wide security policy and authorization information into the signatures and certificates in order to permit the verifier of a signature to decide whether to accept the signature or certificate as valid, thus accommodating and easing electronic commerce business transactions.
It is further desirable to reduce the risks associated with digital signature systems, particularly with end-user smart cards, by building on this use of public key certificates and attribute certificates.
It is further desirable to prevent the use of such a digital signature system by any party that might purport to "accept" a transaction in contravention of the applicable authorization certificates when that party had not signed the applicable "system rules" agreement pertaining to that system of communicating signer authorization.